package leetcode.code0472;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/**
 * 43 / 44 个通过测试用例 状态：超出时间限制 提交时间：1 分钟前
 */
public class Solution implements IDebug {

	Node root;

	public List<String> findAllConcatenatedWordsInADict(String[] words) {
		Arrays.sort(words, (a, b) -> a.length() - b.length());
		List<String> ans = new ArrayList<>();
		root = new Node();
		for (String word : words) {
			if (word.length() == 0) { // 42 / 44
				continue;
			}
			if (root.div(0, word.toCharArray())) {
				ans.add(word);
			} else {
				root.add(word);
			}
		}
		return ans;
	}

	class Node {
		Node[] character;
		boolean words;

		public Node() {
			character = new Node[26];
		}

		public boolean add(String word) {
			char[] w = word.toCharArray();
			Node node = root;
//			List<Integer> starters = new ArrayList<>();
			int len = word.length();
			for (int i = 0; i < len; i++) {
				char c = w[i];
				int index = c - 'a';
				if (node.character[index] == null) {
					node.character[index] = new Node();
				}
				node = node.character[index];
//				if (node.words) {
//					starters.add(i + 1);
//				}
			}
			boolean ans = false;
//			for (int i = 0; i < starters.size(); i++) {
//				int start = starters.get(i);
//				if (div(start, w)) {
//					ans = true;
//					break;
//				}
//			}
			node.words = true;
			return ans;
		}

		public boolean div(int start, char[] w) {
			if (w.length == start) {// 干了就差这一句好像
				return true;
			}
			Node search = root;
			for (int i = start; i < w.length; i++) {
				char c = w[i];
				int index = c - 'a';
				if (search.character[index] == null) {
					return false;
				}
				search = search.character[index];
				if (search.words) {
					if (div(i + 1, w)) {
						return true;
					}
				}
			}
			return false;
		}
	}

	@Override
	public void debug1() {
		List<String> e = HelpDebug.str2liststr("[\"b\",\"c\",\"bc\"]");
		HelpDebug.compare(e, this.findAllConcatenatedWordsInADict(HelpDebug.str2array2("[\"b\",\"c\",\"bc\"]")));

	}

	@Override
	public void debug2() {
		List<String> e = HelpDebug.str2liststr("[\"catsdogcats\",\"dogcatsdog\",\"ratcatdogcat\"]");
		HelpDebug.compare(e, this.findAllConcatenatedWordsInADict(HelpDebug.str2array2(
				"[\"cat\",\"cats\",\"catsdogcats\",\"dog\",\"dogcatsdog\",\"hippopotamuses\",\"rat\",\"ratcatdogcat\"]")));

	}

	@Override
	public void debug3() {
		List<String> e = HelpDebug.str2liststr("[\"catsdogcats\",\"dogcatsdog\",\"ratcatdogcat\"]");
		HelpDebug.compare(e, this.findAllConcatenatedWordsInADict(HelpDebug.str2array2(
				"[\"cat\",\"cats\",\"catsdogcats\",\"dog\",\"dogcatsdog\",\"hippopotamuses\",\"rat\",\"ratcatdogcat\",\"dogcatsdogs\",\"catsdogs\"]")));

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();

	}

}
